/*
clsquare - closed loop simulation system
Copyright (c) 2004, Neuroinformatics Group, Prof. Dr. Martin Riedmiller,
University of Osnabrueck

Author: Martin Riedmiller

All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:

   * Redistributions of source code must retain the above copyright
     notice, this list of conditions and the following disclaimer.
   * Redistributions in binary form must reproduce the above copyright
     notice, this list of conditions and the following disclaimer in
     the documentation and/or other materials provided with the
     distribution.
   * Neither the name of the <ORGANIZATION> nor the names of its
     contributors may be used to endorse or promote products derived
     from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/

#include "valueparser.h"
#include "str2val.h"
#include "tuqute.h"
#include <cstdlib>
#include "maze.h"
#include <cmath>

#define MAX_NUM_ACTIONS 255

#define VERBOSE(xxx) if(verbose) cout <<__PRETTY_FUNCTION__ <<": "<< xxx<<endl

#define LEFT 0
#define RIGHT 1
#define DOWN 2
#define UP 3


/**********************************************************************/
/* interface to clsquare                                               */
/**********************************************************************/

bool Tuqute::get_action(const double* observation, double* action)
{
	//greedy policy

	double values_max[4] = {0};
	int dir = 0;
	double max;
	double obsX = observation[0];
	double obsY = observation[1];

	//LEFT
	//if at border of maze
	if(obsX==0)
		values_max[0] = 0;
	else
		values_max[0] = values[(int)obsX-1][(int)obsY];

	//RIGHT
	//if at border of maze
	if(obsX==state_dim_X-1)
		values_max[1] = 0;
	else
		values_max[1] = values[(int)obsX+1][(int)obsY];

	//DOWN
	//if at border of maze
	if(obsY==state_dim_Y-1)
		values_max[2] = 0;
	else
		values_max[2] = values[(int)obsX][(int)obsY+1];

	//UP
	//if at border of maze
	if(obsY==0)
		values_max[3] = 0;
	else
		values_max[3] = values[(int)obsX][(int)obsY-1];

    //find maximum
	max = values_max[0];
	for(int k=0; k<4; k++)
		if(values_max[k]>max)
		{
			max = values_max[k];
			dir = k;
		}

	//output direction
	action[0] = dir;
	cnt_steps++;
	cnt_steps_episodes++;

    return true;
}

void Tuqute::notify_reward(const double reward)
{
  //VERBOSE("reward="<<reward);
}


bool Tuqute::deinit(){
  VERBOSE("finishing");
  stats_file.close();
  return true;
}

void Tuqute::notify_episode_starts(const double* initial_observation){
  VERBOSE("Episode starts");
  //VERBOSE(cnt_episodes);
  //VERBOSE(initial_observation[0]);
  //VERBOSE(initial_observation[1]);

  if(!converged&&cnt_episodes%start_states==0)
  {
	  //Value-Iteration-step
	  double values_max[4] = {0};
	  double alpha = 0.9;
	  double p = 1 - noise;
	  double max;
	  //threshold for prioritized sweeping
	  double prior_threshold = 0.0;
	  double** values_copy = new double*[state_dim_X];
	  for (int i=0; i<state_dim_X ; i++)
		values_copy[i] = new double[state_dim_Y];

	  //work copy
	  copy_values(values, values_copy);

	  for(int i=0; i<state_dim_X; i++)
	  {
		  for(int j=0; j<state_dim_Y; j++)
		  {
			  //prioritized sweeping; ignored if threshold is 0
			  if(values_old[0][0]==1000||
					  ((i==0||(i!=0&&abs(values[i-1][j]-values_old[i-1][j])>=prior_threshold))||
					  (i==state_dim_X-1||(i!=state_dim_X-1&&abs(values[i+1][j]-values_old[i+1][j])>=prior_threshold))||
					  (j==0||(j!=0&&abs(values[i][j+1]-values_old[i][j+1])>=prior_threshold))||
					  (j==state_dim_Y-1||(j!=state_dim_Y-1&&abs(values[i][j-1]-values_old[i][j-1])>=prior_threshold))))
			  {
			    //LEFT
			    //if at border of maze
				if(i==0)
					values_max[0] = -1;
				else
					values_max[0] = p*(rewards[i][j]+alpha*values[i-1][j]);

				//RIGHT
				//if at border of maze
				if(i==state_dim_X-1)
					values_max[1] = -1;
				else
					values_max[1] = p*(rewards[i][j]+alpha*values[i+1][j]);

				//DOWN
				//if at border of maze
				if(j==0)
					values_max[2] = -1;
				else
					values_max[2] = p*(rewards[i][j]+alpha*values[i][j+1]);

				//UP
				//if at border of maze
				if(j==state_dim_Y-1)
					values_max[3] = -1;
				else
					values_max[3] = p*(rewards[i][j]+alpha*values[i][j-1]);

				//find maximum
				max = values_max[0];
				for(int k=0; k<4; k++)
				  if(values_max[k]>max)
					  max = values_max[k];

				values_copy[i][j] = max;
				//VERBOSE(max);
			  }
			  cout<<values_copy[i][j]<<"  ";
		  }
		  cout<<endl;
	  }


	  //copy values back
	  copy_values(values, values_old);
	  copy_values(values_copy, values);

	  converged = comp_values(values, values_old);
  }

  if(cnt_episodes%start_states==0)
	  cnt_iter++;

  cnt_episodes++;
  if(converged) VERBOSE("Converged!");
};

void Tuqute::notify_episode_stops(const double* final_observation, double final_reward, bool is_terminal_state){
  VERBOSE("Episode stops");


  //evaluation
  	  steps[cnt_episodes%start_states] = cnt_steps;
  	  //VERBOSE(cnt_steps);


  if(cnt_iter%1==0&&cnt_episodes%start_states==0)
  {

	  //calculate average and standard deviation
	  double sdev;
	  //first avg for sdev, second without sdev
	  //int avg = cnt_steps_episodes/cnt_episodes;
	  int avg = cnt_steps_episodes/start_states;

	  for(int i=0; i<=start_states; i++)
	  {
		  sdev += (steps[i] - avg)*(steps[i] - avg);
	  }
	  sdev /= start_states;
	  sdev = sqrt(sdev);
	  stats_file<<cnt_iter<<" "<<avg<<endl;//<<" "<<sdev<<endl;

	  cnt_steps_episodes = 0;
	  //for sdev
	  //cnt_episodes = 0;
  }
  cnt_steps = 0;



};

bool Tuqute::init(const int observation_dim, const int action_dim, double deltat, const char* fname, const char* chapter)
{
  this->observation_dim = observation_dim;
  this->action_dim = action_dim;
  verbose = true;
  converged = false;
  cnt_steps = 0;
  cnt_iter = 0;
  cnt_episodes = 0;
  cnt_steps_episodes = 0;
  start_states = 0;

  bool result = read_options(fname);
  srand48(234);
  VERBOSE("init: got observed_observation_dim: "<<observation_dim<<" and action_dim:"<<action_dim<<" and delta_t: "<<deltat);

  Maze maze;
  int temp;
  double temp1;
  //load maze.def
  maze.init(temp, temp, temp, temp1, "maze.def");
  noise = maze.get_noise();

  this->state_dim_X = maze.get_maze()->get_extend_X();
  this->state_dim_Y = maze.get_maze()->get_extend_Y();
  values = new double*[state_dim_X];
  values_old = new double*[state_dim_X];
  rewards = new int*[state_dim_X];
  for (int i=0; i<state_dim_X ; i++)
  {
      values[i] = new double[state_dim_Y];
      values_old[i] = new double[state_dim_Y];
      rewards[i] = new int[state_dim_Y];
  }

  //fill in values-matrix from maze.def
  for(int i=0; i<state_dim_X; i++)
	  for(int j=0; j<state_dim_Y; j++)
	  {
	  		  //read status from cells in maze and write in rewards
			  temp = maze.get_maze()->get_cell(i, j)->get_status();
			  if(temp == 0)  //obstacle
				  rewards[i][j] = -5;
			  else
			  if(temp == 1)  //free
			  {
			  	  rewards[i][j] = 0;
			      start_states++;
			  }
			  else
			  if(temp == 2)  //goal
			  {
			  	rewards[i][j] = 10;
			  	start_states++;
			  }

			  //initial values
			  values[i][j] = 0;
			  values_old[i][j] = 1000; //signal for start of algo
	  }

  steps = new int[start_states+1];
  steps[0] = 0;

  //stats file
  stats_file.open("stats.dat");
  stats_file<<"#updates of value function   average steps to goal"<<endl;
  //start_states = 3876;
  VERBOSE("init finished");

  return result;
}

bool Tuqute::read_options(const char * fname) {
  char param[255];

  ValueParser vp(fname,"Controller");
  vp.get("verbose",verbose);
  vp.get("actions",param,255);
  parse_actions(param);

  return true;
}

void Tuqute::parse_actions(const char* param)
{
  const char* str = param;
  double val;
  action_def = new double[MAX_NUM_ACTIONS*action_dim];
  actions_in_dim = new int[action_dim];

  for (int i = 0; i<action_dim;i++){
    strskip(str,"[",str);
    int j = 0;
    while(str2val(str,val,str)) {
      action_def[i*MAX_NUM_ACTIONS+j] = val;
      j++;
    }
    actions_in_dim[i] = j;
    strskip(str,"]",str);
  }
}

void Tuqute::copy_values(double** source, double** dest)
{

	for(int i=0; i<state_dim_X; i++)
	{
		for(int j=0; j<state_dim_Y; j++)
		{
			dest[i][j] = source[i][j];
		}
	}
}

bool Tuqute::comp_values(double** values1, double** values2)
{
  int temp, temp1;

	for(int i=0; i<state_dim_X; i++)
	{
		for(int j=0; j<state_dim_Y; j++)
		{
			temp = values1[i][j]*100;
			temp1 = values2[i][j]*100;
			if(temp != temp1)
				return false;
		}
	}

	return true;
}

REGISTER_CONTROLLER(Tuqute, "The controller for homework 1.")
